/**
 * edurender
 * er_hashtable.c
 * (c) 2009 J. Brad Byrd
 */

#include "er_hashtable.h"

#include "er_assert.h"
#include "er_macros.h"
#include "er_memory.h"

#include <stdlib.h>
#include <string.h>

#define BUCKET_COUNT (57)

#define INLINE_KEY_SIZE (16)

typedef struct Node
{
	union
	{
		void *ptr;
		char mem[INLINE_KEY_SIZE];
	} key;
	
	const void *value;
	struct Node *next;
	ERuint hash;
	ERuint keySize;
} Node;

typedef struct
{
	Node *first;
	Node *last;
} Bucket;

struct ERHashTable
{
	ERHashFunc hashFunc;
	EREqualityFunc equalityFunc;
	Bucket buckets[BUCKET_COUNT];
};

static ERbool DefaultEqualityFunc(const void *keyA, ERuint sizeA, const void *keyB, ERuint sizeB)
{
	return (sizeA == sizeB) && (memcmp(keyA, keyB, sizeA) == 0);
}

static Node *Find(ERHashTable *ht, const void *key, ERuint size, Node **previous)
{
	ERuint hash = ht->hashFunc(key, size);
	Node *prev = NULL;
	Node *node = ht->buckets[hash % BUCKET_COUNT].first;

	while (node != NULL)
	{
		if (node->hash == hash)
		{
			ERbool match;

			if (node->keySize > INLINE_KEY_SIZE)
				match = ht->equalityFunc(key, size, node->key.ptr, node->keySize);
			else
				match = ht->equalityFunc(key, size, node->key.mem, node->keySize);
			
			if (match)
			{
				if (previous != NULL)
					*previous = prev;
					
				return node;
			}
		}
	
		prev = node;
		node = node->next;
	}
	
	if (previous != NULL)
		*previous = NULL;
	
	return NULL;
}

ERHashTable *erCreateHashTable(ERHashFunc hashFunc, EREqualityFunc equalityFunc)
{
	ERHashTable *ht;
	Bucket *bucket;
	ERuint i;

	ER_ASSERT(hashFunc);

	ht = (ERHashTable *)ER_MALLOC(sizeof(ERHashTable));
	ER_ASSERT(ht);

	ht->hashFunc = hashFunc;
	ht->equalityFunc = (equalityFunc == NULL) ? DefaultEqualityFunc : equalityFunc;

	bucket = ht->buckets;

	for (i = 0; i < BUCKET_COUNT; i++)
	{
		bucket->first = NULL;
		bucket->last = NULL;
		bucket++;
	}
	
	return ht;
}

void erDestroyHashTable(ERHashTable *ht)
{
	ERuint i;
	Bucket *bucket;
	
	ER_ASSERT(ht);
	
	bucket = ht->buckets;
	
	for (i = 0; i < BUCKET_COUNT; i++)
	{
		Node *node = bucket->first;
		
		while (node != NULL)
		{
			Node *next = node->next;
			ER_FREE(node);
			node = next;
		}
	
		bucket->first = NULL;
		bucket->last = NULL;
		bucket++;
	}
	
	ER_FREE(ht);
}

ERbool erHashTableInsert(ERHashTable *ht, const void *key, ERuint keySize, const void *value)
{
	Bucket *bucket;
	Node *node;
	ERuint hash;

	ER_ASSERT(ht);
	ER_ASSERT(key);

	hash = ht->hashFunc(key, keySize);
	bucket = &ht->buckets[hash % BUCKET_COUNT];
	node = (Node *)ER_MALLOC(sizeof(Node));
	ER_ASSERT(node);
	
	if (bucket->first == NULL)
		bucket->first = node;
	else
		bucket->last->next = node;

	bucket->last = node;

	node->keySize = keySize;
	node->hash = hash;
	node->value = value;
	node->next = NULL;

	if (keySize > INLINE_KEY_SIZE)
	{
		node->key.ptr = ER_MALLOC(keySize);
		ER_ASSERT(node->key.ptr);
		memcpy(node->key.ptr, key, keySize);
	}
	else
		memcpy(node->key.mem, key, keySize);

	return ER_FALSE;
}

void erHashTableRemove(ERHashTable *ht, const void *key, ERuint keySize)
{
	Node *prev;
	Node *node;
	Bucket *bucket;

	ER_ASSERT(ht);
	ER_ASSERT(key);

	bucket = &ht->buckets[ht->hashFunc(key, keySize) % BUCKET_COUNT];
	node = Find(ht, key, keySize, &prev);
	
	if (node)
	{
		if (prev == NULL)
			bucket->first = node->next;
		else
			prev->next = node->next;

		if (node->next == NULL)
			bucket->last = prev;
	
		if (node->keySize > INLINE_KEY_SIZE)
			ER_FREE(node->key.ptr);
		
		ER_FREE(node);
	}
}

ERbool erHashTableSearch(ERHashTable *ht, const void *key, ERuint keySize, const void **value)
{
	Node *node;
	
	ER_ASSERT(ht);
	ER_ASSERT(key);
	
	node = Find(ht, key, keySize, NULL);
	
	if (node)
	{
		if (value)
			*value = node->value;
		
		return ER_TRUE;
	}
	
	if (value)
		*value = NULL;
	
	return ER_FALSE;
}

void erHashTableIterate(ERHashTable *ht, ERHashTableIterator *it)
{
	ER_UNUSED(ht);
	ER_UNUSED(it);
}
